package com.huangyi;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        //被围绕的区域
        class Solution {
            int m, n;
            // 四联通方向：右、左、下、上
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};

            public void solve(char[][] board) {
                if (board == null || board.length == 0) return;
                m = board.length;
                n = board[0].length;

                // 1) 从四条边把连通的 'O' 标成 'A'
                for (int j = 0; j < n; j++) {
                    if (board[0][j] == 'O') bfsO2A(board, 0, j);
                    if (board[m - 1][j] == 'O') bfsO2A(board, m - 1, j);
                }
                for (int i = 1; i < m - 1; i++) {
                    if (board[i][0] == 'O') bfsO2A(board, i, 0);
                    if (board[i][n - 1] == 'O') bfsO2A(board, i, n - 1);
                }

                // 2) 全表替换：未标记的 O -> X；已标记的 A -> O
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (board[i][j] == 'O') board[i][j] = 'X';
                        else if (board[i][j] == 'A') board[i][j] = 'O';
                    }
                }
            }

            // 把与 (si, sj) 同团的 'O' 全部标记为 'A'
            private void bfsO2A(char[][] board, int si, int sj) {
                Queue<int[]> q = new LinkedList<>();
                q.offer(new int[]{si, sj});
                board[si][sj] = 'A';            // 入队即标记，避免重复入队

                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    int a = cur[0], b = cur[1];
                    for (int k = 0; k < 4; k++) {
                        int x = a + dx[k], y = b + dy[k];
                        if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                            board[x][y] = 'A';  // 入队前先标记
                            q.offer(new int[]{x, y});
                        }
                    }
                }
            }
        }


        //迷宫中离出口最近的路口
        class Solution2 {
            int m, n;
            boolean[][] vis;
            int[] dx = {0, 0, -1, 1};
            int[] dy = {1, -1, 0, 0};

            public int nearestExit(char[][] maze, int[] entrance) {
                if (maze == null || maze.length == 0) return -1;
                m = maze.length;
                n = maze[0].length;
                vis = new boolean[m][n];

                int sx = entrance[0], sy = entrance[1];
                Queue<int[]> q = new LinkedList<>();
                q.offer(new int[]{sx, sy});
                vis[sx][sy] = true;

                int steps = 0; // 已走的层数（步数）
                while (!q.isEmpty()) {
                    int size = q.size(); // 固定本层大小
                    for (int k = 0; k < size; k++) {
                        int[] cur = q.poll();
                        int a = cur[0], b = cur[1];

                        // 出队即判断是否为出口（边界空格且非入口自身）
                        if ((a == 0 || a == m - 1 || b == 0 || b == n - 1)
                                && !(a == sx && b == sy)) {
                            return steps;
                        }

                        // 扩展四邻
                        for (int i = 0; i < 4; i++) {
                            int x = a + dx[i], y = b + dy[i];
                            if (x >= 0 && x < m && y >= 0 && y < n
                                    && maze[x][y] == '.'
                                    && !vis[x][y]) {
                                vis[x][y] = true;          // 入队即标记
                                q.offer(new int[]{x, y});
                            }
                        }
                    }
                    steps++; // 本层处理完，步数 +1
                }
                return -1; // 无出口可达
            }
        }
    }
}